home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1994 March / Internet Info CD-ROM (Walnut Creek) (March 1994).iso / inet / internet-drafts / draft-ietf-idmr-igmp-dense-00.txt < prev    next >
Text File  |  1993-10-29  |  21KB  |  481 lines
  1.  
  2.  
  3. IDMR Working Group                                     Steve Deering
  4. INTERNET-DRAFT                                            Xerox PARC
  5. Expires April 1993                                    Deborah Estrin
  6. <draft-ietf-idmr-igmp-dense-00.txt>                          USC/ISI
  7.                                                       Dino Farinacci
  8.                                                        cisco Systems
  9.                                                         Van Jacobsen
  10.                                                                  LBL
  11.                                                     October 10, 1993
  12.  
  13.  
  14.      IGMP Router Extensions for Routing to Dense Multicast-Groups
  15.  
  16.  
  17. Status of this Memo
  18.  
  19.    This document is an Internet Draft.  Internet Drafts are working
  20.    documents of the Internet Engineering Task Force (IETF), its Areas,
  21.    and its Working Groups. Note that other groups may also distribute
  22.    working documents as Internet Drafts).
  23.  
  24.    Internet Drafts are draft documents valid for a maximum of six
  25.    months. Internet Drafts may be updated, replaced, or obsoleted by
  26.    other documents at any time.  It is not appropriate to use Internet
  27.    Drafts as reference material or to cite them other than as a "working
  28.    draft" or "work in progress."
  29.  
  30.    Please check the I-D abstract listing contained in each Internet
  31.    Draft directory to learn the current status of this or any other
  32.    Internet Draft.
  33.  
  34.  
  35. 1.0 Introduction
  36.  
  37. This specification defines a multicast routing algorithm for multicast
  38. groups that are densely distributed across an internet. The protocol is
  39. unicast routing protocol independent. It is based on ESL sparse-mode
  40. [Estrin93] and employs the same packet formats. This protocol is called
  41. dense-mode ESL. The design is based largely on foundational work by
  42. Deering [Deering91].
  43.  
  44.  
  45. 2.0. Overview
  46.  
  47. Dense-mode ESL uses Reverse Path Multicasting (RPM). RPM is a technique
  48. in which a multicast datagram is forwarded if the receiving interface is
  49. one used to forward unicast datagrams to the source of the datagram. The
  50. multicast datagram is then forwarded out all other interfaces.
  51. Dense-mode ESL builds source-based acyclic trees.
  52.  
  53. Dense-mode ESL is data driven, whereby it is assumed that all downstream
  54. systems want to receive multicast datagrams. For densely populated
  55. groups this is optimal. If some areas of the network do not have group
  56. members, dense-mode ESL will prune branches of the source-based tree.
  57. When group members leave the group, branches will also be pruned.
  58.  
  59. Unlike DVMRP [DVMRP] packets are forwarded on all outgoing interfaces
  60. (except the incoming) until pruning and truncation occurs. DVMRP makes
  61. use of parent-child data to reduce the number of outgoing interfaces
  62. used before pruning. In both protocols, once truncation occurs pruning
  63. state is maintained and packets are only forwarded onto outgoing
  64. interfaces that in fact reach downstream members.
  65.  
  66. We chose to accept additional overhead in favor of reduced dependency on
  67. the unicast routing protocol, and reduced overall protocol complexity.
  68.  
  69. Dense-mode ESL differs from sparse-mode ESL in two essential points: 1)
  70. there are no periodic joins transmitted, only explicit triggered prunes,
  71. and 2) there is no Rendezvous Point (RP).
  72.  
  73.  
  74. 3.0. Background
  75.  
  76. Reverse Path Broadcasting (RPB) is different from RPF because duplicate
  77. packets are avoided in the former that are sent in the latter. In
  78. general, the number of duplicates sent on a link can be as high as the
  79. number of routers directly connected to that link.
  80.  
  81. Reverse Path Multicasting (RPM) is different from RPF or RPB because
  82. pruning information is propagated upstream. Leaf routers must know that
  83. they are leaf routers so that in response to no IGMP reports for a
  84. group, those leaf routers know to initiate the prune process.
  85.  
  86. In DVMRP there are routing protocol dependencies for a) building a
  87. parent-child database so that duplicate packets can be eliminated, b)
  88. eliminating duplicate packets on multi-access LANs, and c) sending "split
  89. horizon with poison reverse" information to detect that a router is not a
  90. leaf router (if a router does not receive any poison reverse messages
  91. from other routers on a multi-access LAN then that router acts as a leaf
  92. router for that LAN and knows to prune if there are not IGMP reports on
  93. that LAN for a group G).
  94.  
  95. Dense-mode ESL will accept some duplicate packets in order to avoid
  96. being routing protocol dependent and avoid building a child parent
  97. database.
  98.  
  99. We introduce a simple prune mechanism for reducing duplicates on 
  100. multi-access LANs.
  101.  
  102. We introduce an alternative leaf-router detection mechanism that does
  103. not rely on a specific unicast routing protocol mechanism such as split
  104. horizon with poison reverse.
  105.  
  106. These mechanisms are described below.
  107.  
  108.  
  109. 4.0 Protocol Description
  110.  
  111. 4.1  Leaf network detection
  112.  
  113. In DVMRP poison reverse information tells a router that other routers on
  114. the shared LAN use the LAN as their incoming interface. As a result,
  115. even if the DR for that LAN does not hear any IGMP Reports for a group,
  116. the DR will know to continue to forward multicast data packets to that
  117. group, and NOT to send a prune message to its upstream neighbor.
  118.  
  119. Since dense-mode ESL does not rely on any unicast routing protocol
  120. mechanisms, this problem is solved by using prune messages sent upstream
  121. on a LAN. If a downstream router on a LAN determines that it has no more
  122. downstream members for a group, then it can multicast a prune message on
  123. the LAN. 
  124.  
  125. A leaf router detects that there are no members downstream when it is the
  126. only router on a network and there are no IGMP Host-Report messages
  127. received from hosts. It determines there are no other routers by not
  128. receiving ESL Router-Query messages.
  129.  
  130. When a prune message is sent on an upstream LAN, it is data link
  131. multicast and IP addressed to the all routers group address (224.0.0.1).
  132. The router to process the prune will be indicated by inserting its
  133. address in the "Address" field of the message.  The address is obtained
  134. by an RPF lookup from the unicast routing table.  When the prune message
  135. is sent, the expected upstream router will schedule a deletion request
  136. of the LAN from its outgoing interfaces for the (S,G) entry from the
  137. prune list.
  138.  
  139. Note the special case for equal-cost paths. When an upstream router is
  140. chosen by an RPF lookup there may be equal-cost paths. The higher IP
  141. addressed system is always chosen. If the unicast routing protocol does
  142. not store all available equal-cost paths in the routing table, the
  143. "Address" field may contain the address of the wrong upstream router. To
  144. avoid this situation, the "Address" field may optionally be set to 0.0.0.0
  145. which means that all upstream routers (the ones that have the LAN as an
  146. outgoing interface for the (S,G) entry) may process the packet.
  147.   
  148. Other routers on the LAN will hear the prune message and respond with a
  149. join if they still expect multicast datagrams from the expected upstream
  150. router. The ESL-Join message is data link multicast and IP addressed to
  151. the all routers group address (224.0.0.1). The router to process the
  152. join will be indicated by inserting its address in the "Address" field
  153. of the message. The address is determined by an RPF lookup from the
  154. unicast routing table. When the expected router receives the join
  155. message, it will cancel the deletion request.
  156.  
  157. Routers will randomly generate a join message delay timer. If a join is
  158. heard from another router before a router sends its own, it will cancel
  159. sending its own join. This will reduce traffic on the LAN.
  160.  
  161. If the expected upstream router does not receive any ESL-Join messages
  162. before the schedule time for the deletion request expires, it deletes
  163. the outgoing LAN interface from the (S,G) multicast forwarding entry.
  164.  
  165. If an (S,G) entry contains an empty outgoing interface list, a prune is
  166. sent upstream. Prune information is flushed periodically. This (or a
  167. loss of state) causes the packets to be sent in RPF mode again which in
  168. turn triggers prune messages.
  169.  
  170.  
  171. 4.2 New members joining an existing group
  172.  
  173. If a router is directly connected to a host that wants to become a
  174. member of a group, the router may optionally, multicast a ESL-Join
  175. message towards known sources. This allows join latency to be reduced
  176. below that indicated by the relatively large timeout value suggested for
  177. prune information.
  178.  
  179. If a receiving router has an entry for (S,G), it adds the interface on
  180. which the IGMP Report or ESL-Join was received. If the (S,G) entry
  181. was a negative cache entry, the router sends an ESL-Join upstream
  182. towards S. This is done for all (Si,G) entries.
  183.  
  184. If routers have no state for (*,G), they do nothing since dense-mode ESL
  185. will deliver a multicast datagram to all interfaces when creating state
  186. about a group.
  187.  
  188. Any routers receiving the ESL-Join that uses the received interface as
  189. an incoming interface for any (Si,G) entry, will not add the interface
  190. to the outgoing interface list.
  191.  
  192. The ESL-Join message is transmitted unreliably.
  193.  
  194.  
  195. 4.3 Protocol Scenario
  196.  
  197. A multicast datagram is sent by a source host. If a receiving router
  198. has no forwarding cache entry for G, it creates (S,G) and (*,G)
  199. entries.  (*,G)->incoming = NULL and (*,G)->outgoing set to all other
  200. interfaces on the router that have either multicast hosts or routers
  201. present.  (S,G)->incoming = interface from RPF lookup. (S,G)->outgoing
  202. is copied from (*,G)->outgoing minus the (S,G)->incoming.
  203.  
  204. An ESL-Prune message is triggered when an (S,G) entry is built with an
  205. empty outgoing interface list. This type of entry is called a negative
  206. cache entry. This can occur when a leaf router has no local members for
  207. group G or a prune message was received from a downstream router which
  208. causes the outgoing interface list to become NULL. ESL-Prune messages
  209. are never sent in response to a received multicast packet that is
  210. associated with a negative cache entry.
  211.  
  212. ESL-Prune messages received on a point to point link are not delayed
  213. before processing as they are in the LAN procedure. If the prune is
  214. received on an interface that is in the outgoing interface list, it is
  215. deleted immediately.  Otherwise it is ignored.
  216.  
  217.  
  218. 4.4 Designated Router election
  219.  
  220. The dense-mode ESL designated router (DR) election uses the same
  221. procedure as in sparse-mode ESL. A DR is necessary for each multi-access LAN
  222. so a single router sends IGMP Host-Query messages to solicit host group
  223. membership.
  224.  
  225. Each ESL router connected to a multi-access LAN should transmit ESL
  226. Router-Query messages every 30 seconds onto the LAN to support DR
  227. election. The highest addressed router becomes the DR.  The ESL routers
  228. discovered should be timed out after 90 seconds. If the DR goes down, a
  229. new DR is elected.
  230.  
  231. DR election is only necessary on multi-access networks. It is not
  232. required that ESL Query messages be sent on point-to-point links.
  233.  
  234.  
  235. 4.5 Parallel paths to a source
  236.  
  237. Two or more routers may receive the same multicast datagram that was
  238. replicated upstream. In particular, if two routers have equal cost paths
  239. to a source and are connected on a common multi-access network,
  240. duplicate datagrams will travel downstream onto the LAN. Dense-mode ESL
  241. will detect such a situation and will not let it persist.
  242.  
  243. If a router receives a multicast datagram on a multi-access LAN from a
  244. source whose corresponding (S,G) outgoing interface list includes the
  245. received interface, the packet must be a duplicate. In this case the
  246. highest IP addressed system should be elected to be forwarder for this
  247. (S,G) entry. When such a datagram is received, it triggers an
  248. ESL-Assert message to be multicast to 224.0.0.2 on the LAN.  Each
  249. router that uses the LAN as an outgoing interface for (S,G) will
  250. compare the source IP address from the message with its own. If its
  251. own address is smaller, it will delete the interface from the outgoing
  252. interface list for the (S,G) entry.  Otherwise, it has been elected as
  253. forwarder and will keep the interface in the entry.
  254.  
  255. This mechanism assures that only one router will forward multicast datagrams
  256. from S to G onto the LAN.
  257.  
  258. Interfaces that are pruned due to Assert processing should have a
  259. shorter timer associated with it compared to the timer that is used when
  260. an interface is pruned due to receipt of ESL-Prune message. This is
  261. recommended so unicast routing changes upstream do not cause long lived
  262. black holes.
  263.  
  264. Assert messages are data link multicast and IP addressed to the all
  265. routers group address 224.0.0.1.
  266.  
  267.  
  268. 4.6 Timing out multicast forwarding entries
  269.  
  270. Each (S,G) and (*,G) entry has timers associated with it. During this time
  271. source-based tree state is kept in the network.
  272.  
  273. There should be multiple timers set. One for the multicast routing entry
  274. itself and one for each interface in the outgoing interface list. The
  275. outgoing interface stays active in the list as long as there is
  276. multicast traffic for the entry or there is an explicit join received
  277. on the interface. If neither occurs the interface will be deleted from
  278. the list after 90 seconds, by default.
  279.  
  280. Once all interfaces in the outgoing interface list are not active, a
  281. timer should be set for the (S,G) entry. During this time the entry is
  282. known as a negative state entry at which a prune is triggered. Once the
  283. (S,G) entry times out, it can be recreated when the next multicast
  284. packet or join arrives.
  285.  
  286.  
  287. 5.0 Sparse mode compatibility
  288.  
  289. There are two issues to consider when dealing with dense-mode ESL and
  290. sparse-mode ESL interaction.
  291.  
  292.     - Is a group part dense and part sparse (dual-mode).
  293.     - If a group is either dense-only or sparse-only, when should it
  294.       transition to the other mode.
  295.  
  296.  
  297. 5.1 Dual-mode
  298.  
  299. If a group has membership qualities where it is densely populated in
  300. some areas of the network and sparsely populated in others, it will have
  301. to be in both modes for the group. If a group has one or more RP
  302. addresses associated with it, either dynamically determined or through
  303. configuration, it will operate in sparse-mode. In addition, if any
  304. interface is configured as a dense-mode interface for the group, the
  305. router will also operate in dense-mode. The group is known to be in 
  306. dual-mode.
  307.  
  308. In dual-mode, a (*,G) entry's outgoing interfaces are built from the
  309. union of dense-mode configured interfaces and interfaces where ESL-Join
  310. messages have been received. A (*,G) entry's incoming interface is
  311. always set to NULL. An (S,G) entry's outgoing interfaces are always
  312. copied from the (*,G) entry's outgoing interfaces. A (S,G) entry's
  313. incoming interface is based on the interface determined by an RPF lookup
  314. when a multicast packet is received for a (*,G) entry.
  315.  
  316. Outgoing interface entries are only timed out if they are not dense-mode
  317. configured interfaces. Typically, these are interfaces that were created
  318. from an sparse-mode ESL-Join. The interface is kept active by periodic
  319. receipts on ESL-Join messages from downstream routers.
  320.  
  321. If an ESL-Join is received on a dense-mode configured interface, it
  322. should be propagated upstream if there is no (S,G) or (*,G) entry.
  323. Otherwise, it is ignored.
  324.  
  325. Periodic ESL-Join and Prune messages are sent upstream if the interface
  326. is not configured in dense-mode. Otherwise, periodic messages are not
  327. sent.
  328.  
  329. A router that is upstream from the RP, will send ESL-Register messages
  330. to the RP if there is one configured for an associated group.  The
  331. Register messages may travel on dense-mode configured interfaces.
  332.  
  333.  
  334. 5.2 Mode Transitioning - from one mode to another
  335.  
  336. When a router decides the mode for a group is not efficient, it may want
  337. to change to the alternate mode or dual-mode.
  338.  
  339. 1) An upstream router can change a downstream interface from sparse to 
  340.    dense without informing downstream router. This change indicates that
  341.    the upstream router doesn't require periodic Joins/Prunes or
  342.    Registers to keep multicast cache entries from timing out. The
  343.    downstream router can stop sending periodic messages when told that
  344.    the mode has changed. However, this action is not required.
  345.  
  346. 2) An upstream router needs to tell a downstream router when going from
  347.    dense to sparse so the downstream router can start sending periodic
  348.    messages.
  349.  
  350. An upstream router sends an ESL-Mode message to neighboring downstream
  351. routers indicating that it wants to change the mode for their common
  352. network. The mode attribute is for all (Si,G). A receiving router is required
  353. to acknowledge the ESL-Mode message with an ESL-ModeAck.
  354.  
  355. ESL-Mode messages are initially multicast and later retransmitted as
  356. unicast on multi-access LANs if an acknowledgement is not received.
  357.  
  358. Downstream routers that receive an ESL-Mode message switch their
  359. incoming interface to the mode indicated in the message. Upstream
  360. routers unilaterally control the mode.
  361.  
  362. Sparse-mode ESL RP-Reachable messages must be sent to all downstream
  363. interfaces regardless if they are in dense or sparse mode. This allows
  364. any downstream sparse-mode router to determine if the RP is still
  365. reachable. An RP-Reachable message is sent downstream in response to a
  366. received ESL-Join with the RP address in the source join list part of
  367. the message.
  368.  
  369.  
  370. 6.0 Message Types
  371.  
  372. ESL messages are encapsulated in IGMP. IGMP runs on top of IP.
  373.  
  374. The following table enumerates the IGMP messages used in each mode.
  375.  
  376.                                Sparse-mode         Dense-mode
  377. (1) Host Membership Query          Sent               Sent
  378. (2) Host Membership Report           -                  - 
  379. (4) Router ESL
  380.     (0) Query                  Sent/Received            -
  381.     (1) Register               Sent/Received            -
  382.     (2) Join/Prune             Sent/Received*      Sent/Received** 
  383.     (3) RP-Reachable           Sent/Received            -
  384.     (4) Assert                       -             Sent/Received
  385.     (5) Mode                   Sent/Received***    Sent/Received***
  386.     (6) ModeAck                Sent/Received***    Sent/Received***
  387.  
  388. *   Sent periodically
  389. **  Sent only triggered by event
  390. *** Sent and received only if Mode Transitioning is supported
  391.  
  392.  
  393. 6.1 Code field addition to IGMP packet format
  394.  
  395.        0                   1                   2                   3
  396.        0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  397.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  398.       |Version| Type  |     Code      |           Checksum            |
  399.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  400.       |                            Address                            |
  401.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  402.  
  403.       A Code field has replaced the Unused field to support the
  404.       variations of the Router ESL message. The Code should be set to
  405.       0 and ignored on receipt for all Types other than type 4.
  406.  
  407.       Hosts must ignore the Code field.
  408.  
  409.       Code values:
  410.  
  411.       0 - Query
  412.  
  413.           "Address" is set to 0 and ignored on receipt.
  414.  
  415.       1 - Register
  416.  
  417.           Used in sparse-mode. Refer to ESL sparse-mode specification.
  418.  
  419.       2 - Join/Prune
  420.  
  421.           Regular sparse-mode/dense-mode Join/Prune list for adding or
  422.           deleting branches to/from a source or RP-based distribution
  423.       tree. The format is in the ESL sparse-mode specification.
  424.  
  425.       When "Address" is used by dense-mode for leaf network
  426.       detection, it contains the IP address of the router which
  427.       processes the Join or Prune. Otherwise, it is set to 0 and
  428.       ignored on receipt.
  429.  
  430.       3 - RP-reachable
  431.  
  432.           Used in sparse-mode. Refer to ESL sparse-mode specification.
  433.  
  434.       4 - Assert
  435.  
  436.       This message is used for electing one of multiple parallel routers
  437.           for downstream forwarding on a multi-access LAN. The body of
  438.       this message is identical to the Join/Prune (2) format.
  439.  
  440.       5 - Mode 
  441.  
  442.       This message is used by an upstream router to inform
  443.       downstream neighbors its desireability to change modes.
  444.       "Address" is set to the group address the mode is associated with.
  445.  
  446.       6 - ModeAck
  447.  
  448.           This message is sent by a downstream router to a neighboring
  449.       upstream router that has previously sent an ESL-Mode message.
  450.       This acknowledges the ESL-Mode message was received without
  451.       error. "Address" is set to the group address the mode is
  452.       associated with.
  453.       
  454.  
  455. 7.0 References
  456.  
  457. [Deering91] S.E. Deering. Multicast Routing in a Datagram Internetwork.
  458.             PhD thesis, Electrical Engineering Dept., Stanford University, 
  459.             December 1991.
  460.  
  461. [DVMRP]     RFC 1075, Distance Vector Multicast Routing Protocol. 
  462.             Waitzman, D., Partridge, C., Deering, S.E, November 1988
  463.  
  464. [Estrin93]  IGMP Router Extensions for Routing to Spare Multicast-Groups,
  465.             S. Deering, D. Estrin, D. Farinacci, V. Jacobson, September 1993  
  466.  
  467. [RFC1112]   Host Extensions for IP Multicasting, Network Working Group, 
  468.             RFC 1112, S. Deering, August 1989
  469.  
  470.  
  471. 8.0 Interoperability Issues
  472.  
  473. 1) MSOPF/ESL-DM interaction
  474. 2) DVMRP/ESL-DM interaction
  475. 3) ESL over NBMA links
  476.    - Either still do BMA procedure with data link replication
  477.    - (S,G) entries need to have neighbor IP addresses
  478.    - Do we IP unicast or just data link unicast
  479.  
  480. ------------------------------------------------------------------------
  481.